package LeetCodeQuestionBank;

import java.util.Stack;

/**
 * 617. 合并二叉树
 * 给你两棵二叉树： root1 和 root2 。
 *
 * 想象一下，当你将其中一棵覆盖到另一棵之上时，两棵树上的一些节点将会重叠（而另一些不会）。你需要将这两棵树合并成一棵新二叉树。合并的规则是：如果两个节点重叠，那么将这两个节点的值相加作为合并后节点的新值；否则，不为 null 的节点将直接作为新二叉树的节点。
 *
 * 返回合并后的二叉树。
 *
 * 注意: 合并过程必须从两个树的根节点开始。
 *
 *
 *
 * 示例 1：
 *
 *
 * 输入：root1 = [1,3,2,5], root2 = [2,1,3,null,4,null,7]
 * 输出：[3,4,5,5,4,null,7]
 * 示例 2：
 *
 * 输入：root1 = [1], root2 = [1,2]
 * 输出：[2,2]
 *
 *
 * 提示：
 *
 * 两棵树中的节点数目在范围 [0, 2000] 内
 * -104 <= Node.val <= 104
 */
public class T617 {
    //执行用时：2 ms, 在所有 Java 提交中击败了15.21%的用户
    //使用 栈进行 深度优先遍历
    public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {

        if (root1 == null) {
            return root2;
        }
        if (root2 == null) {
            return root1;
        }


        //tree1 的栈
        Stack<TreeNode> stack1 = new Stack<>();
        //tree2 的栈
        Stack<TreeNode> stack2 = new Stack<>();


        stack1.add(root1);
        stack2.add(root2);

        //开始同步遍历两颗树
        while (!stack1.isEmpty() && !stack2.isEmpty()) {

            //1树 的节点
            TreeNode node1 = stack1.pop();
            //2树 的节点
            TreeNode node2 = stack2.pop();

            //将两个节点的值相加 赋值给1树的节点 返回1树 作为结果
            node1.val = node1.val + node2.val;

            if (node1.left != null || node2.left != null) {

                //左节点都存在
                if (node1.left != null && node2.left != null) {
                    stack1.add(node1.left);
                    stack2.add(node2.left);
                } else if (node1.left == null) { //如果1树节点的左节点没有 2树的做节点有
                    //直接把node2的左节点 给node1
                    node1.left = node2.left;
                }

            }

            if (node1.right != null || node2.right != null) {

                if (node1.right != null && node2.right != null) {
                    stack1.add(node1.right);
                    stack2.add(node2.right);
                } else if (node1.right == null) {
                    node1.right = node2.right;
                }
            }

        }

        return root1;


    }

    //方法2 使用递归实现dfs
    //执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
    public TreeNode mergeTrees2(TreeNode root1, TreeNode root2) {

        if (root1 == null) {
            return root2;
        }
        if (root2 == null) {
            return root1;
        }

        TreeNode treeNode = new TreeNode(root1.val + root2.val);

        treeNode.left = mergeTrees2(root1.left, root2.left);
        treeNode.right = mergeTrees2(root1.right, root2.right);

        return treeNode;
    }


    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }


}
